package summer.dp;

public class Solution115 {
    public int numDistinct(String s, String t) {
        int l1 = s.length();
        int l2 = t.length();
        int[][] dp = new int[l1 + 1][l2 + 1];
        for (int i = 0; i < l1; i++) {
            dp[i][0] = 1;

        }
        for (int i = 0; i < l1; i++) {
            for (int j = 0; j < l2; j++) {
                if (s.charAt(i) == t.charAt(j)) dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
                else dp[i + 1][j + 1] = dp[i][j + 1];
            }
        }
        return dp[l1][l2];
    }
}
